package mid.array;

/**
 *
 * <p>
 *     盛最多的水的容器
 * </p>
 *
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。
 * 在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。
 * 找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 */
public class q11 {

    public static void main(String[] args) {
        int[] array1 = {1,8,6,2,5,4,8,3,7};
        System.out.println(letCodeMaxArea(array1));
        int[] array2 = {1,1};
        System.out.println(letCodeMaxArea(array2));
        int[] array3 = {4,3,2,1,4};
        System.out.println(letCodeMaxArea(array3));
        int[] array4 = {1,2,1};
        System.out.println(letCodeMaxArea(array4));
    }


    /**
     * 双指针算法
     * @param height
     * @return
     */
    public static int letCodeMaxArea(int[] height) {
        int l = 0;
        int r = height.length - 1;
        int max = 0;
        while (l < r) {
            int area = Math.min(height[l], height[r]) * (r - l);
            max = Math.max(max, area);
            if (height[l] <= height[r]) {
                ++l;
            } else {
                --r;
            }
        }
        return max;
    }


    public static int maxArea(int[] height) {

        int maxArea = 0;
        int maxY = 0;

        for (int i = 0; i < height.length - 1; i++) {
            int x1 = i + 1;
            int y1 = height[i];
            if (i == 0) {
                for (int j = i + 1; j < height.length; j++) {
                    int x2 = j + 1;
                    int y2 = height[j];
                    int area = doArea(x1, y1, x2, y2);
                    maxArea = Math.max(maxArea, area);
                }
                maxY = y1;
            } else {
                if (y1 > maxY) {
                    for (int j = i + 1; j < height.length; j++) {
                        int x2 = j + 1;
                        int y2 = height[j];
                        int area = doArea(x1, y1, x2, y2);
                        maxArea = Math.max(maxArea, area);
                    }
                    maxY = y1;
                }
            }
        }
        return maxArea;
    }

    private static int doArea(int x1, int y1, int x2, int y2) {
        return Math.min(y1, y2) * (x2 - x1);
    }

}
